//#define _CRT_SECURE_NO_WARNINGS 1
//
//#include<stdio.h>
//
////void Swap(int* p1, int* p2)
////{
////	int tem = *p1;
////	*p1 = *p2;
////	*p2 = tem;
////}
////int PartionSort1(int* a, int begin, int end)
////{
////	int keyi = begin;
////	while (begin < end)
////	{
////		while (begin < end && a[end] >= a[keyi])
////		{
////			end--;
////		}
////		while (begin < end && a[begin] <= a[keyi])
////		{
////			begin++;
////		}
////		Swap(&(a[begin]), &(a[end]));
////	}
////	Swap(&(a[begin]), &(a[keyi]));
////	keyi = begin;
////	return keyi;
////}
////
////
////
//
//
////void QuickSort1(int* a, int begin, int end)
////{
////	int left = begin;
////	int right = end;
////	if (left >= right)
////	{
////		return;
////	}
////	int keyi = PartionSort1(a, begin, end);
////	QuickSort1(a, begin, keyi - 1);
////	QuickSort1(a, keyi+1, end);
////}
//
////void QuickSort4(int* a, int begin, int end)
////{
////	int left = begin;
////	int right = end;
////	if (left >= right)
////		return;
////	int prev = begin;
////	int cur = begin + 1;
////	int keyi = begin;
////	while (cur <= end)
////	{
////		if (a[cur] < a[keyi] && ++prev != cur)
////			Swap(&(a[cur]), &(a[prev]));
////		cur++;
////	}
////	Swap(&(a[prev]), &(a[keyi]));
////	keyi = prev;
////	QuickSort4(a, begin, keyi - 1);
////	QuickSort4(a, keyi + 1, end);
////}
//void Swap(int* p1, int* p2)
//{
//	int tem = *p1;
//	*p1 = *p2;
//	*p2 = tem;
//}
//
//int GetMidi(int* a, int begin, int end)
//{
//	int mid = (begin + end) / 2;
//	if (a[begin] < a[mid])
//	{
//		if (a[mid] < a[end])
//		{
//			return mid;
//		}
//		else if (a[begin] < a[end])
//		{
//			return end;
//		}
//		else
//		{
//			return begin;
//		}
//	}
//	else//a[begin] > a[mid]
//	{
//		if (a[mid] > a[end])
//		{
//			return mid;
//		}
//		else if (a[begin] > a[end])
//		{
//			return end;
//		}
//		else
//		{
//			return begin;
//		}
//	}
//}
//
//int  PartionSort3(int* a, int begin, int end)
//{
//	int prev = begin;
//	int keyi = begin;
//	int cur = begin + 1;
//	int midi = GetMidi(a, begin, end);
//	Swap(&(a[keyi]), &(a[midi]));
//	while (cur <= end)
//	{
//		if (a[cur] < a[keyi] && ++prev != cur)
//			Swap(&(a[cur]), &(a[prev]));
//		cur++;
//	}
//	Swap(&(a[keyi]), &(a[prev]));
//	keyi = prev;
//	return keyi;
//
//}
//
//void QuickSort3(int* a, int begin, int end)
//{
//	int left = begin;
//	int right = end;
//	if (left >= right)
//	{
//		return;
//	}
//	int keyi = PartionSort3(a, begin, end);
//	QuickSort3(a, begin, keyi - 1);
//	QuickSort3(a, keyi + 1, end);
//}
//int main()
//{
//
//	int a[10] = { 9, 7 ,8,6,5,4,3,2,1,0 };
//	//QuickSort1(a, 0, sizeof(a) / sizeof(int) - 1);
//	QuickSort3(a, 0, sizeof(a) / sizeof(int) - 1);
//	/*QuickSort4(a, 0, sizeof(a) / sizeof(int) - 1);*/
//	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
//	{
//		printf("%d ", a[i]);
//	}
//	return 0;
//}

